package algorithms.que11;

import edu.princeton.cs.algs4.StdRandom;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @功能
 * @创建时间 2020/6/7
 */
public class que39 {
    public static int sum;

    public static void main1(String[] args) {
        //     int[] arr=new int[]{1,2,3,3,4};
        //    System.out.println(count( arr, 3));
        //         char[] a = " 1".toCharArray();
        int a = 1;
        int b = 2;
        double c = ((double) a + b) / 2;
        System.err.println(c);
        //       System.err.println(lengthOfLongestSubstring(" 1"));
    }

    @Test
    public void sss() {
        String a = "bqdasdasfadsfff";
        System.err.println(findMaxPalindrome(a));
    }

    String findMaxPalindrome(String s) {
        Boolean[] p = new Boolean[s.length()];
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                //每次刷新pj
                p[j] = s.charAt(i) == s.charAt(j) && (i - j < 3 || p[j+1]);
                if(p[j]&&i-j+1>res.length()){
                    res = s.substring(j,i+1);
                }
            }
        }
        return res;
//        boolean isSame = false;
//        int start = 0;
//        int end = 0;
//        String res = "";
//        String s1 = new StringBuffer(s).reverse().toString();
//        for (int i = 0; i < s.length(); i++) {
//            if (!isSame && s.charAt(i) == s1.charAt(i)){
//                isSame = true;
//                start = i;
//            }else if(isSame && s.charAt(i) != s1.charAt(i)){
//                isSame = false;
//                res = s.substring(start,i).length() > res.length() ? s.substring(start,i):res;
//            }
//        }
//        return res;
//        int n = s.length();
//        String res = "";
//        boolean[] P = new boolean[n];
//        for (int i = n - 1; i >= 0; i--) {
//            for (int j = n - 1; j >= i; j--) {
//                P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
//                if (P[j] && j - i + 1 > res.length()) {
//                    res = s.substring(i, j + 1);
//                }
//            }
//        }
//        return res;
    }

    void findMaxPalindrome(String s, int index, String[] ints, Map<String, Boolean> map) {
        for (int i = index; i < s.length(); i++) {
            String tmp = s.substring(index, i + 1);
            if (isPalindrome(tmp, map, index, i + 1)) {
                ints[i - index + 1] = tmp;
            }
            findMaxPalindrome(s, index + 1, ints, map);
        }
    }

    boolean isPalindrome(String s, Map<String, Boolean> map, int start, int end) {
        if (map.get(start + "," + end) != null && map.get(start + "," + end) == true) {
            return false;
        }
        char[] chars = s.toCharArray();
        int mid = chars.length / 2 + 1;
        for (int i = 0; i < mid; i++) {
            if (chars[i] != chars[chars.length - 1 - i]) {
                map.put(start + "" + end, true);
                return false;
            }
        }
        return true;
    }

    public static int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int start = 0;
        int end = 0;
        int max = 0;
        for (; end < chars.length; end++) {
            for (int i = start; i < end; i++) {
                if (chars[i] == chars[end]) {
                    max = Math.max(end - start, max);
                    start = i + 1;
                }

            }
            if (end == chars.length - 1) {
                max = Math.max(end - start + 1, max);
            }
        }
        return max;
    }

    public static void www(int T, int N) {
        int[] a = new int[N];
        int[] b = new int[N];
        for (int i = 0; i < T; i++) {
            for (int j = 0; j < N; j++) {
                a[j] = 100000 + StdRandom.uniform(99999);
                b[j] = 100000 + StdRandom.uniform(99999);
            }
            for (int j = 0; j < N; j++) {
                //            System.out.println(count(a, b[j]));
                if (count(a, b[j]) != -1) {
                    sum += count(a, b[j]);
                }
            }
        }
        System.out.println(sum);
    }

    public static int count(int[] arr, int key) {
        int start = 0;
        int end = arr.length - 1;
        int count = 0;
        int tmp = 0;
        while (start <= end) {
            int middle = (start + end) / 2;
            if (key < arr[middle]) {
                end = middle - 1;
            } else if (key > arr[middle]) {
                start = middle + 1;
            } else {
                tmp = middle;
                while (key == arr[middle]) {
                    middle--;
                    count++;
                }
                while (key == arr[tmp + 1]) {
                    tmp++;
                    count++;
                }
                return count;
            }
        }
        return -1;
    }
}